package linkedlist.test86;

import listbyorder.utils.ListNode;

/**
 * 分隔链表
 * @author code_yc
 * @version 1.0
 * @date 2020/7/14 13:50
 */
public class Solution1 {

    public ListNode partition(ListNode head, int x) {
        // 将链表分成两个链表之后合并
        if (head == null || head.next == null) return head;
        ListNode s = new ListNode(-1);
        ListNode h = new ListNode(-1);
        ListNode t = head;
        ListNode sc = s, hc = h;
        while (t != null) {
            if (t.val < x) {
                sc.next = t;
                sc = sc.next;
            } else {
                hc.next = t;
                hc = hc.next;
            }
            t = t.next;
        }
        hc.next = null;
        sc.next = h.next;
        return s.next;
    }
}
